1. Field of the Disclosure
The disclosure relates generally to data communications, and in particular, to an improved method and apparatus for preventing flow starvation with Weighted Fair Queuing.
2. The Prior Art
Background
Control of packet flow in routers is one important task in the management of networks.
FIG. 1 shows an example of a prior art communication system. FIG. 1 shows a sender and a receiver connected to a network cloud. For purposes of this disclosure, the sender and receiver may be any standard electronic devices which desire to communicate through an electronic network such as the Internet, a Local Area Network (LAN), or a Wide Area Network (WAN).
To the end user, the operation of the system in FIG. 1 should be transparent and error free. For example, an end user (receiver) watching streaming video originating from a video server (sender) should never know what is taking place within the network cloud that makes the process possible.
FIG. 2 is a more detailed diagram of a prior art communications system. FIG. 2 expands on the detail of FIG. 1 by showing an example of communications occurring over a standard Internet connection. FIG. 2 includes a host and a server connected to a network cloud comprising a plurality of routers. In FIG. 2, the host wishes to transmit a packet P to the server. As is known by those of ordinary skill in the art, when the packet P arrives at router 1, the router 1 will encode the packet P with a unique identifier containing the source and destination addresses. Then router 1 will forward the packet P onto the destination through other routers according to standard routing protocols. In this example, router 1 will forward packet P onto router 4, which will then forward the packet P onto the ultimate destination, which in our example here is the server.
Increasing bandwidth demands can cause performance degradations in packet-based systems. FIG. 3 is a diagram of a prior art system with two packet streams P and M each including packets 1–N competing for bandwidth. To fairly allocate limited bandwidth between competing packet flows, a prior art process known as Weighted Fair Queuing may be employed.
As is known by those of ordinary skill in the art, Weighted Fair Queuing is process whereby priority may be given to some flows in favor of others by assigning an ID to the packets of the flows prior to the packets being queued at the egress point of the router. The ID is computed from characteristics that uniquely identify a particular packet flow and provides multiple levels of flow priority while ensuring that the order of egress and ingress of the flows is maintained.
In a typical scenario, packets to be sent are sorted on a flow basis with several flows competing for egress based on the ID of the packet at the head of the flow. For efficient sorting, IDs are assigned in a monotonically increasing manner, with packets having smaller ID numbers queued first. A packet ID S may be assigned using an algorithm such as:S=(W+(T*D)>>scale)  Eq. 1                Where: S=ID or sequence number;        W=Wallclock, such as a local clock, or the ID of the last packet transmitted;        T=Type of Service Factor; and        D=Datagram size in bytes.        
In Eq. 1, “scale” is a divisor to bring the (T*D) factor into a reasonable number such that it does not make “S” wrap around too quickly. As is appreciated by those of ordinary skill in the art, the “>>” is taken from the C or Java programming languages, and means “shift right by so many bits”. In essence, it is division by (2scale). The >>scale operator will be so used and defined throughout this disclosure.
However, the ID has a finite word length, resulting in an absolute maximum ID value. Thus, when the number of queued packets exceeds the absolute limit, the ID numbers will be forced to ‘wrap’ around and repeat, resulting in flows having both high-number packets and low-numbered packets. This will confuse the sorting logic, as the low-numbered packets will be treated as having a high priority while the high-numbered packets will be treated as having a low priority, resulting in some packets which properly should be given a later queue time being placed at the head of the queue.
Under high demands, some flows may be starved of service for a brief period, as the ID numbers cycle wrap around. In a worst-case scenario, some flows may be starved of service completely. As will be appreciated by those skilled in the art, high end or faster routers will experience these problems sooner than low end or slower routers because of the faster rates of packet de-queuing.
FIGS. 4A–4D are diagrams illustrating weighted fair queuing according to the prior art. The illustration begins in FIG. 4A, which shows a series of flows in a queue waiting to be transmitted. The next packet to be transmitted in FIG. 4A is S#1503 from Flow#20 which is at the head of the queue.
Continuing in FIG. 4B, packet with S#1503 has now been transmitted. However, the flows have now been re-sorted, and hence Flow#3 now has a packet S#1588 at the head of the queue. Note that flow #72 has a packet S#2988. In this example, we will assume that 3000 is the highest number that may be assigned. Thus, in the scenario of FIGS. 4A–4D, the ID numbers are close to wrapping around.
In FIG. 4C, packet S#1588 of Flow#3 has not yet been transmitted. However, a new packet for Flow#3 has arrived after the sequence numbers have wrapped around 3000, and has been assigned a sequence number of S#103.
Finally, in FIG. 4D, packets with S#1588, 1622 and 1681 have now been transmitted. Simultaneously, multiple packets for Flow#3 have arrived. Because of the wrap around of the sequence number, the packets of Flow #3 are all assigned low sequence numbers.
Thus, Flows #20, #238, etc. with packets having higher sequence numbers, although they arrived much earlier and should have been scheduled for earlier transmission, will be starved of service for a period of time. If sequence numbers did not wrap around at 3000, the packets of Flow#3 would have numbers 3103, 3207, 3311 and 3415. Thus, they would properly be queued later than the earlier the arriving packets.